from typing import List


# 300. 最长递增子序列
# 给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
# 子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。
# 例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列
# 。
def lengthOfLIS(nums: List[int]) -> int:
    # dp数组
    dp = [1]
    for num_index in range(1, len(nums)):

        cur = nums[num_index]

        max_dp = dp[0]

        # 只需要遍历 dp 数组，只要发现当前 num 大于 dp 数组，对应的那个数，递增序列 + 1
        for dp_index in range(num_index):

            if cur > nums[dp_index]:
                max_dp = max(dp[dp_index] + 1, max_dp)

        dp.append(max_dp)

    # 不一定是最后一个数，可能是中间的某个数
    return max(dp)


nums_1 = [0, 1, 0, 1, 0, 1, 0, 1]
result = lengthOfLIS(nums_1)
print(f"result:{result}")

nums_1 = [10, 9, 2, 5, 3, 7, 101, 18]
result = lengthOfLIS(nums_1)
print(f"result:{result}")

nums_1 = [0, 1, 0, 3, 2, 3]
result = lengthOfLIS(nums_1)
print(f"result:{result}")

nums_1 = [7, 7, 7, 7, 7, 7, 7]
result = lengthOfLIS(nums_1)
print(f"result:{result}")

nums_1 = [11, 12, 13, 14, 1, 2, 3]
result = lengthOfLIS(nums_1)
print(f"result:{result}")

nums_1 = [11, 12, 13, 14, 1, 2, 3, 4]
result = lengthOfLIS(nums_1)
print(f"result:{result}")

nums_1 = [11, 12, 13, 14, 1, 2, 3, 4, 5]
result = lengthOfLIS(nums_1)
print(f"result:{result}")

nums_1 = [1, 3, 6, 7, 9, 4, 10, 5, 6]
result = lengthOfLIS(nums_1)
print(f"result:{result}")
